#! /usr/bin/python
# coding=utf-8
import time


# 统计时间


def timeit(func):
    def wrapper(*args, **kwargs):
        start = time.clock()
        result = func(*args, **kwargs)
        end = time.clock()
        print('used:%s ms' % (end - start))
        return result

    return wrapper


def fib(n):
    """
    朴素自顶向下递归
    """
    return 1 if n == 1 or n == 2 else fib(n - 2) + fib(n - 1)


# fibonacci结果表
tab = [0, 1, 1] + [0 for _ in range(1 << 20)]
print(len(tab))  # 1048576


def fib_dp(n):
    """
    因为自顶向下的递归会有大量的重复计算，
    采用空间换时间的策略.
    使用一个tab保存fib(n)的值，位置i存储f(i)的结果
    在计算之前检查表格，不存在才计算,可以显著提高性能
    """
    if n > 2 and tab[n] == 0:
        tab[n] = fib_dp(n - 1) + fib_dp(n - 2)
    return tab[n]


def fib_dp_bottom2up(n):
    F = [0, 1, 1] + [-1 for _ in range(n)]
    if n < 0:
        return 0
    """
    自底向上循环,和人工写下的顺序一致
    """
    if n > 2:
        for i in range(3, n + 1):
            F[i] = F[i - 2] + F[i - 1]
    return F[n]


@timeit
def main(n):
    print("n=" + str(n), fib(n))


@timeit
def main_dp(n):
    print("main_dp n=" + str(n), fib_dp(n))


@timeit
def main_dp2(n):
    print("main_dp2 n=" + str(n), fib_dp_bottom2up(n))


if __name__ == '__main__':
    main(1)
    main(3)
    main(10)
    main(30)
    # main(60)
    main_dp(1)
    main_dp(3)
    main_dp(10)
    main_dp(100)
    main_dp(1000)
    main_dp2(4)
    main_dp2(100)
    main_dp2(1000)
    main_dp2(40)
